{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize Number of Subsequences in a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSubsequenceCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串中最多数目的子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的字符串&nbsp;<code>text</code>&nbsp;和另一个下标从 <strong>0</strong>&nbsp;开始且长度为 <code>2</code>&nbsp;的字符串&nbsp;<code>pattern</code>&nbsp;，两者都只包含小写英文字母。</p>\n",
    "\n",
    "<p>你可以在 <code>text</code>&nbsp;中任意位置插入 <strong>一个</strong> 字符，这个插入的字符必须是&nbsp;<code>pattern[0]</code>&nbsp;<b>或者</b>&nbsp;<code>pattern[1]</code>&nbsp;。注意，这个字符可以插入在 <code>text</code>&nbsp;开头或者结尾的位置。</p>\n",
    "\n",
    "<p>请你返回插入一个字符后，<code>text</code>&nbsp;中最多包含多少个等于 <code>pattern</code>&nbsp;的 <strong>子序列</strong>&nbsp;。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>text = \"abdcdbc\", pattern = \"ac\"\n",
    "<b>输出：</b>4\n",
    "<strong>解释：</strong>\n",
    "如果我们在 text[1] 和 text[2] 之间添加 pattern[0] = 'a' ，那么我们得到 \"ab<em><strong>a</strong></em>dcdbc\" 。那么 \"ac\" 作为子序列出现 4 次。\n",
    "其他得到 4 个 \"ac\" 子序列的方案还有 \"<em><strong>a</strong></em>abdcdbc\" 和 \"abd<em><strong>a</strong></em>cdbc\" 。\n",
    "但是，\"abdc<em><strong>a</strong></em>dbc\" ，\"abd<em><strong>c</strong></em>cdbc\" 和 \"abdcdbc<em><strong>c</strong></em>\" 这些字符串虽然是可行的插入方案，但是只出现了 3 次 \"ac\" 子序列，所以不是最优解。\n",
    "可以证明插入一个字符后，无法得到超过 4 个 \"ac\" 子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>text = \"aabb\", pattern = \"ab\"\n",
    "<b>输出：</b>6\n",
    "<strong>解释：</strong>\n",
    "可以得到 6 个 \"ab\" 子序列的部分方案为 \"<em><strong>a</strong></em>aabb\" ，\"aa<em><strong>a</strong></em>bb\" 和 \"aab<em><strong>b</strong></em>b\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= text.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>pattern.length == 2</code></li>\n",
    "\t<li><code>text</code> 和&nbsp;<code>pattern</code>&nbsp;都只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-number-of-subsequences-in-a-string](https://leetcode.cn/problems/maximize-number-of-subsequences-in-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-number-of-subsequences-in-a-string](https://leetcode.cn/problems/maximize-number-of-subsequences-in-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abdcdbc\"\\n\"ac\"', '\"aabb\"\\n\"ab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        if pattern[0] == pattern[1]:\n",
    "            x = text.count(pattern[0])\n",
    "            x += 1\n",
    "            return x * (x - 1) // 2\n",
    "        else:\n",
    "            x = text.count(pattern[0])\n",
    "            y = text.count(pattern[1])\n",
    "            z = c = 0\n",
    "            for s in text:\n",
    "                if s == pattern[0]:\n",
    "                    c += 1\n",
    "                elif s == pattern[1]:\n",
    "                    z += c\n",
    "            return z + max(x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        if pattern[0] == pattern[1]:\n",
    "            return (cnt := text.count(pattern[0])) * (cnt + 1) >> 1\n",
    "        cnt1, cnt2, ans = text.count(pattern[0]), text.count(pattern[1]), 0\n",
    "        if cnt1 < cnt2: ans = cnt2\n",
    "        else: cnt2 += 1\n",
    "        for c in text:\n",
    "            if   c == pattern[0]: ans += cnt2\n",
    "            elif c == pattern[1]: cnt2 -= 1       \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        f=Counter(text)\n",
    "        a=f[pattern[0]]\n",
    "        b=f[pattern[1]]\n",
    "        if pattern[0]==pattern[1]:\n",
    "            return (a+1)*a//2    \n",
    "        \n",
    "        c=0\n",
    "        ans=0\n",
    "        for x in text:\n",
    "           if x==pattern[0]:\n",
    "              c+=1\n",
    "           elif x==pattern[1]:\n",
    "               ans+=c\n",
    "        return ans+max(a,b)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        a, b = pattern\n",
    "        if a != b:\n",
    "            cnt_a = cnt_b = total = 0\n",
    "            for c in text:\n",
    "                if c == a:\n",
    "                    cnt_a += 1\n",
    "                elif c == b:\n",
    "                    cnt_b += 1\n",
    "                    total += cnt_a\n",
    "        else:\n",
    "            return comb(text.count(a) + 1, 2)\n",
    "        return total + max(cnt_a, cnt_b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        if pattern[0] == pattern[1]:\n",
    "            cnt = text.count(pattern[0])\n",
    "            return cnt * (cnt + 1) // 2\n",
    "        cnt0, cnt1 = text.count(pattern[0]), text.count(pattern[1])\n",
    "        ans = 0\n",
    "        if cnt0 < cnt1:\n",
    "            ans = cnt1  # 把pattern[0]放在最左边\n",
    "        else:\n",
    "            cnt1 += 1   # 把pattern[1]放在最右边\n",
    "        for c in text:\n",
    "            if c == pattern[0]:\n",
    "                ans += cnt1\n",
    "            elif c == pattern[1]:\n",
    "                cnt1 -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        a, b = pattern\n",
    "        ans1 = 0    # a + text\n",
    "        ans2 = 0    # text + b\n",
    "        c = [0, 0]\n",
    "        for x in text:\n",
    "            if x == b:\n",
    "                ans1 += c[0] + 1\n",
    "                ans2 += c[0]\n",
    "                c[1] += 1\n",
    "                if a == b: c[0] += 1\n",
    "            elif x == a:\n",
    "                c[0] += 1\n",
    "                if a == b: c[1] += 1\n",
    "        ans2 += c[0]\n",
    "        \n",
    "        return max(ans1, ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        x, y = pattern[0], pattern[1]\n",
    "        if x == y:\n",
    "            c = text.count(x)\n",
    "            return c * (c + 1) // 2\n",
    "        res = cx = cy = 0\n",
    "\n",
    "        for i in text:\n",
    "            if i == x:\n",
    "                cx += 1\n",
    "            elif i == y:\n",
    "                cy += 1\n",
    "                res += cx\n",
    "        return res + max(cx, cy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        cnt0, cnt1 = 0, 0\n",
    "        res = 0\n",
    "        for c in text:\n",
    "            if c == pattern[1]:\n",
    "                res += cnt0\n",
    "                cnt1 += 1\n",
    "            if c == pattern[0]:\n",
    "                cnt0 += 1\n",
    "        \n",
    "        return res + max(cnt0, cnt1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        C = Counter(text)\n",
    "        c1,c2 = pattern[0],pattern[1]\n",
    "        if c1 == c2:\n",
    "            return comb(C[c1]+1,2)\n",
    "        \n",
    "        res = 0\n",
    "        mx = C[c2]\n",
    "        temp = mx\n",
    "        for i in text:\n",
    "            if i == c1:\n",
    "                temp += mx\n",
    "            if i == c2:\n",
    "                mx -= 1\n",
    "        res = max(res,temp)\n",
    "        \n",
    "        temp = 0\n",
    "        mx = C[c2]+1\n",
    "        strt = 1\n",
    "        for i in text:\n",
    "            if i == c1:\n",
    "                temp += mx\n",
    "            if i == c2:\n",
    "                mx -= 1\n",
    "        res = max(res,temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        a, b = pattern\n",
    "        if a != b:\n",
    "            cnt_a = cnt_b = total = 0\n",
    "            for c in text:\n",
    "                if c == a:\n",
    "                    cnt_a += 1\n",
    "                elif c == b:\n",
    "                    cnt_b += 1\n",
    "                    total += cnt_a\n",
    "            return total + max(cnt_a, cnt_b)\n",
    "        else:\n",
    "            return comb(text.count(a) + 1, 2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        a, b = pattern\n",
    "        ans1 = 0    # a + text\n",
    "        ans2 = 0    # text + b\n",
    "        c = Counter()\n",
    "        for x in text:\n",
    "            if x not in pattern:\n",
    "                continue\n",
    "            if x == b:\n",
    "                ans1 += c[a] + 1\n",
    "                ans2 += c[a]\n",
    "            c[x] += 1\n",
    "        ans2 += c[a]\n",
    "        \n",
    "        return max(ans1, ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        a1, a2 = pattern[0], pattern[1]\n",
    "\n",
    "        cnt1 = cnt2 = 0\n",
    "        ans = 0\n",
    "        for w in text:\n",
    "            if w == a2:\n",
    "                cnt2 += 1\n",
    "                ans += cnt1\n",
    "\n",
    "            if w == a1:\n",
    "                cnt1 += 1\n",
    "\n",
    "        return ans + max(cnt1, cnt2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        a, b = pattern\n",
    "        if a == b:\n",
    "            return comb(text.count(a) + 1, 2)\n",
    "        cnt_a = cnt_b = total = 0\n",
    "        for c in text:\n",
    "            if c == a:\n",
    "                cnt_a += 1\n",
    "            elif c == b:\n",
    "                cnt_b += 1\n",
    "                total += cnt_a\n",
    "        return total + max(cnt_a, cnt_b)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        def get(s):\n",
    "            res = cnt = 0 \n",
    "            for i in s:\n",
    "                if i == pattern[1]:\n",
    "                    res += cnt \n",
    "                if i == pattern[0]:\n",
    "                    cnt += 1 \n",
    "            return res \n",
    "        return max(get(pattern[0] + text), get(text + pattern[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        x = pattern[0]\n",
    "        y = pattern[1]\n",
    "        n = len(text)\n",
    "        xcnt,ycnt = 0, 0\n",
    "        total = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            c = text[i]\n",
    "            if c==x:\n",
    "                total += ycnt\n",
    "                xcnt+=1\n",
    "            if c==y:\n",
    "                ycnt+=1\n",
    "        return total+max(xcnt,ycnt)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        n = len(text)\n",
    "        ct_a, ct_b = 0, 0\n",
    "        res = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            c = text[i]\n",
    "            if c == pattern[0]:\n",
    "                res += ct_b\n",
    "                ct_a += 1\n",
    "            if c == pattern[1]:\n",
    "                ct_b += 1\n",
    "        return res + max(ct_a, ct_b)\n",
    "             \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "\n",
    "        n = len(text)\n",
    "        x, y = list(pattern)[:] \n",
    "        def check():\n",
    "            res = 0\n",
    "            pre = 0\n",
    "            for ww in s:\n",
    "                if ww == y:\n",
    "                    res += pre\n",
    "                if ww == x:\n",
    "                    pre += 1\n",
    "            return res\n",
    "        s = text\n",
    "        ans = check()\n",
    "        cur = s.count(y)\n",
    "        cur2 = s.count(x)\n",
    "        return ans + cur if cur > cur2 else cur2+ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        c1 = ret = 0\n",
    "        c2 = 0\n",
    "        for x in text:\n",
    "            \n",
    "            if x == pattern[1]:\n",
    "                ret += c1\n",
    "                c2 += 1\n",
    "            if x == pattern[0]:\n",
    "                c1 += 1\n",
    "        return ret + max(c1, c2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        tmp = pattern[0] + text\n",
    "        n = len(tmp)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        s = 0\n",
    "        for c in tmp:\n",
    "            if c == pattern[1]:\n",
    "                s += cnt\n",
    "            if c == pattern[0]:\n",
    "                cnt += 1\n",
    "        ans = max(ans, s)\n",
    "        tmp = text + pattern[1]\n",
    "        cnt = 0\n",
    "        s = 0\n",
    "        for c in tmp:\n",
    "            if c == pattern[1]:\n",
    "                s += cnt\n",
    "            if c == pattern[0]:\n",
    "                cnt += 1\n",
    "        ans = max(ans, s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        c1 = text.count(pattern[0])\n",
    "        c2 = text.count(pattern[1])\n",
    "        if c1 > c2:\n",
    "            text += pattern[1]\n",
    "        else:\n",
    "            text = pattern[0] + text\n",
    "        c = 0\n",
    "        s = 0\n",
    "        for i in range(len(text)):\n",
    "            if text[i] == pattern[1]:\n",
    "                s += c\n",
    "            if text[i] == pattern[0]:\n",
    "                c += 1\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        if pattern[0] == pattern[1]:\n",
    "            return (cnt := text.count(pattern[0])) * (cnt + 1) >> 1\n",
    "\n",
    "        temp = ''\n",
    "        n = len(text)\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        res = 0\n",
    "\n",
    "        for x in text:\n",
    "            if x == pattern[0]:\n",
    "                p1 += 1\n",
    "            elif x == pattern[1]:\n",
    "                p2 += 1\n",
    "            temp += x\n",
    "        \n",
    "        if n == p1:\n",
    "            return p1\n",
    "        elif n == p2:\n",
    "            return p2\n",
    "\n",
    "        for i, x in enumerate(temp):\n",
    "            if x != pattern[0]:\n",
    "                continue\n",
    "            res += temp[i+1:].count(pattern[1])\n",
    "\n",
    "        if p1 > p2:\n",
    "            res += p1\n",
    "        else:\n",
    "            res += p2\n",
    "\n",
    "        return res         \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        n = len(text)\n",
    "        ct_a, ct_b = 0, 0\n",
    "        res = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            c = text[i]\n",
    "            if c == pattern[0]:\n",
    "                res += ct_b\n",
    "                ct_a += 1\n",
    "            if c == pattern[1]:\n",
    "                ct_b += 1\n",
    "        return res + max(ct_a, ct_b)\n",
    "             \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        cnt1 = cnt2 = 0\n",
    "        res = 0\n",
    "        for char in text:\n",
    "            if char == pattern[1]:\n",
    "                res += cnt1\n",
    "                cnt2 += 1\n",
    "            if char == pattern[0]:\n",
    "                cnt1 += 1\n",
    "        \n",
    "        return res + max(cnt1, cnt2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        count_1 = count_2 = 0\n",
    "        ans = 0\n",
    "        for i in range(len(text) - 1, -1, -1):\n",
    "            if text[i] == pattern[1]: count_2 += 1\n",
    "            elif text[i] == pattern[0]:\n",
    "                ans += count_2\n",
    "                count_1 += 1\n",
    "        return ans + max(count_1, count_2) if pattern[1] != pattern[0] else count_2 * (count_2 + 1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        if pattern[0] == pattern[1]:\n",
    "            n = text.count(pattern[0])\n",
    "            return n * (n + 1) // 2\n",
    "        res = 0\n",
    "        n0, n1 = 0, 0\n",
    "        for c in text:\n",
    "            if c == pattern[0]:\n",
    "                n0 += 1\n",
    "            elif c == pattern[1]:\n",
    "                n1 += 1\n",
    "                res += n0\n",
    "        return res + max(n0, n1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, s: str, t: str) -> int:\n",
    "        n = len(s)\n",
    "        cnta, cntb, ans = 0, 0, 0\n",
    "        for c in s:\n",
    "            if c == t[1]:\n",
    "                ans += cnta\n",
    "                cntb += 1\n",
    "            if c == t[0]:\n",
    "                cnta += 1\n",
    "        return ans + max(cnta, cntb)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        n = len(text)\n",
    "        p1 = pattern[0]\n",
    "        p2 = pattern[1]\n",
    "        ans = 0\n",
    "        cnt_p1, cnt_p2 = 0, 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if text[i] == p2:\n",
    "                cnt_p2 += 1\n",
    "            elif text[i] == p1:\n",
    "                cnt_p1 += 1\n",
    "                ans += cnt_p2\n",
    "        if p1 == p2:\n",
    "            ans = (1 + cnt_p1 + cnt_p2) * (cnt_p1 + cnt_p2) // 2\n",
    "        else:\n",
    "            ans += max(cnt_p1, cnt_p2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        a=pattern[0]\n",
    "        b=pattern[1]\n",
    "        if a==b:\n",
    "            ans=text.count(a)+1\n",
    "            return ans*(ans-1)//2\n",
    "\n",
    "        c0=0\n",
    "        c1=text.count(b)\n",
    "        ans=0 \n",
    "        for ch in text:\n",
    "            if ch!=a and ch!=b:\n",
    "                continue\n",
    "            if ch==a:\n",
    "                c0+=1\n",
    "            if ch==b:\n",
    "                c1-=1\n",
    "                ans+=c0\n",
    "        return ans+max(text.count(a),text.count(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        if pattern[0] == pattern[1]:\n",
    "            m = text.count(pattern[0])\n",
    "            if m < 1: return 0\n",
    "            m += 1\n",
    "            return m * (m - 1) // 2\n",
    "        tmp = pattern[0] + text\n",
    "        n = len(tmp)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        s = 0\n",
    "        for i, c in enumerate(tmp):\n",
    "            cnt += c == pattern[0]\n",
    "            if c == pattern[1]:\n",
    "                s += cnt\n",
    "        ans = max(ans, s)\n",
    "        tmp = text + pattern[1]\n",
    "        cnt = 0\n",
    "        s = 0\n",
    "        for i, c in enumerate(tmp):\n",
    "            cnt += c == pattern[0]\n",
    "            if c == pattern[1]:\n",
    "                s += cnt\n",
    "        ans = max(ans, s)\n",
    "        if pattern[0] == pattern[1]:\n",
    "            if ans == 1: return 0\n",
    "            else: return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "\n",
    "        a, b = pattern[0], pattern[1]\n",
    "        cnta, cntb = 0, 0\n",
    "        ans = 0\n",
    "        for ch in text:\n",
    "            if a == b:\n",
    "                if ch == a:\n",
    "                    ans += cnta\n",
    "                    cnta += 1\n",
    "                    \n",
    "            else:\n",
    "                if ch == a:\n",
    "                    cnta += 1\n",
    "                elif ch == b:\n",
    "                    cntb += 1\n",
    "                    ans += cnta\n",
    "                    \n",
    "        # print(cnta, cntb, ans)\n",
    "        return max(ans + cnta, ans + cntb)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        new_text = ''\n",
    "        for c in text:\n",
    "            if c in pattern:\n",
    "                new_text += c\n",
    "        a, b = pattern[0], pattern[1]\n",
    "        cnt = {a:new_text.count(a), b:new_text.count(b)}\n",
    "        res = 0\n",
    "        n = len(new_text)\n",
    "        if n == 0: return 0\n",
    "        if a == b:\n",
    "            # print(new_text, cnt[a])\n",
    "            res = int((cnt[a]+1)*cnt[a]/2)\n",
    "            return res\n",
    "        ca, cb = 0, 0\n",
    "        for c in new_text:\n",
    "            if c == a:\n",
    "                ca += 1\n",
    "            else:\n",
    "                cb += 1\n",
    "                res += ca\n",
    "        res += max(ca, cb)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        a, b = pattern\n",
    "        s = ''.join(x for x in text if x in pattern)\n",
    "        def count(s):\n",
    "            ans = 0\n",
    "            c = Counter()\n",
    "            for j,v in enumerate(s):\n",
    "                if v == b:\n",
    "                    ans += c[a]\n",
    "                c[v] += 1\n",
    "            return ans\n",
    "        \n",
    "        return max(count(a+s), count(s+b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        sLen = len(text)\n",
    "        cnt = []\n",
    "        ans = 0\n",
    "        numA = 0\n",
    "        for i in range(sLen):\n",
    "            if text[i] == pattern[0]:\n",
    "                numA += 1\n",
    "            elif text[i] == pattern[1]:\n",
    "                cnt.append(numA)\n",
    "        #print(cnt, numA)\n",
    "        if pattern[0] != pattern[1]:\n",
    "            ans = max(sum(cnt) + len(cnt), sum(cnt)+numA)\n",
    "        else:\n",
    "            ans = (numA+1)*numA//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        if pattern[0] == pattern[1]:\n",
    "            cnt = text.count(pattern[0])\n",
    "            return comb(cnt + 1, 2)\n",
    "        a, b = [], deque()\n",
    "        for i, j in enumerate(text):\n",
    "            if j == pattern[0]:\n",
    "                a.append(i)\n",
    "            elif j == pattern[1]:\n",
    "                b.append(i)\n",
    "        base = 0\n",
    "        ln_a, ln_b = len(a), len(b)\n",
    "        r = 0\n",
    "        for i in a:\n",
    "            while b and b[0] < i:\n",
    "                b.popleft()\n",
    "            if not b:\n",
    "                break \n",
    "            base += len(b)\n",
    "        return base + max(ln_a, ln_b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        ans = 0\n",
    "        n, m = len(text), 2\n",
    "        if pattern[0] == pattern[1]:\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                if text[i] == pattern[0]:\n",
    "                    cnt += 1\n",
    "            ans = (1 + cnt) * cnt // 2\n",
    "            return ans\n",
    "        first_arr = []\n",
    "        second_arr = []\n",
    "        for i in range(n):\n",
    "            if text[i] == pattern[0]:\n",
    "                first_arr.append(i)\n",
    "            elif text[i] == pattern[1]:\n",
    "                second_arr.append(i)\n",
    "        s, t = len(first_arr), len(second_arr)\n",
    "        first_arr.insert(0, -1)\n",
    "        cnt = 0\n",
    "        for i in range(s + 1):\n",
    "            index = bisect.bisect_right(second_arr, first_arr[i])\n",
    "            cnt += t - index\n",
    "        first_arr.pop(0)\n",
    "        ans = max(ans, cnt)\n",
    "        cnt = 0\n",
    "        second_arr.insert(t, n)\n",
    "        for i in range(s):\n",
    "            index = bisect.bisect_right(second_arr, first_arr[i])\n",
    "            cnt += t - index + 1\n",
    "        second_arr.pop()\n",
    "        ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        if pattern[0] == pattern[1]:\n",
    "            r = 1\n",
    "            for ch in text:\n",
    "                if ch == pattern[0]:\n",
    "                    r += 1\n",
    "            return r * (r - 1) // 2\n",
    "        record = [[0, 0]]\n",
    "        op = -1\n",
    "        n = len(text)\n",
    "        for i in range(n):\n",
    "            if op == -1:\n",
    "                if text[i] == pattern[0]:\n",
    "                    op = 0\n",
    "                    record[-1][0] += 1\n",
    "                elif text[i] == pattern[1]:\n",
    "                    op = 1\n",
    "                    record[-1][1] += 1\n",
    "            elif op == 0:\n",
    "                if text[i] == pattern[0]:\n",
    "                    record[-1][0] += 1\n",
    "                elif text[i] == pattern[1]:\n",
    "                    op = 1\n",
    "                    record[-1][1] += 1\n",
    "            elif op == 1:\n",
    "                if text[i] == pattern[0]:\n",
    "                    op = 0\n",
    "                    record.append([1, 0])\n",
    "                elif text[i] == pattern[1]:\n",
    "                    record[-1][1] += 1\n",
    "        k = len(record)\n",
    "        sum1 = sum([record[i][1] for i in range(k)])\n",
    "        sum2 = sum([record[i][0] for i in range(k)])\n",
    "        s1 = sum1\n",
    "        s = 0\n",
    "        for i in range(k):\n",
    "            s += record[i][0] * s1\n",
    "            s1 -= record[i][1]\n",
    "        return s + max(sum1, sum2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        index0, index1 = [], []\n",
    "        for i, t in enumerate(text):\n",
    "            if t == pattern[0]:\n",
    "                index0.append(i)\n",
    "            if t == pattern[1]:\n",
    "                index1.append(i)\n",
    "        cnt = 0\n",
    "        for ind in index1:\n",
    "            cnt += bisect.bisect_left(index0, ind)\n",
    "        return cnt + max(len(index0), len(index1))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:\n",
    "        cnt = 0\n",
    "        record1 = [0]*len(text)\n",
    "        record2 = [0]*len(text)\n",
    "        for i in range(len(text)-1, -1, -1):\n",
    "            if text[i]==pattern[1]:\n",
    "                cnt += 1\n",
    "            record1[i] = cnt\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(len(text)):\n",
    "            if text[i]==pattern[0]:\n",
    "                cnt += 1\n",
    "            record2[i] = cnt\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(text)-1):\n",
    "            if text[i]==pattern[0]:\n",
    "                res += record1[i+1]\n",
    "        append = 0\n",
    "        if len(record1):\n",
    "            append = record1[0]\n",
    "        for i in range(len(text)):\n",
    "            append = max(append, record1[i])\n",
    "        \n",
    "        if len(record2):\n",
    "            append = max(append, record2[-1])\n",
    "        for i in range(len(text)-1,-1,-1):\n",
    "            append = max(append, record2[i])\n",
    "        return res+append"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
